#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

#include <iostream>
using namespace std;

struct listNode {
    int data;
    listNode* next;
    listNode* prev;

    listNode(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
private:
    listNode* head;
    listNode* tail;
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    
    ~DoublyLinkedList() {
        clear();
    }

    listNode* getHead() const { return head; }
    listNode* getTail() const { return tail; }
    
    void clear() {
        listNode* current = head;
        while (current) {
            listNode* nextNode = current->next;
            delete current;
            current = nextNode;
        }
        head = tail = nullptr;
    }
    
    listNode* getNodeAt(int position) const {
        if (position <= 0) return nullptr;
        
        listNode* current = head;
        int count = 1;
        while (current && count < position) {
            current = current->next;
            count++;
        }
        return current;
    }
    
    int getLength() const {
        int length = 0;
        listNode* current = head;
        while (current) {
            length++;
            current = current->next;
        }
        return length;
    }

    void insertAtHead(int val) {
        listNode* newNode = new listNode(val);
        if (!head) {
            head = tail = newNode;
        }
        else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        cout << "在头部插入: " << val << endl;
    }
    
    void insertAtTail(int val) {
        listNode* newNode = new listNode(val);
        if (!tail) {
            head = tail = newNode;
        }
        else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        cout << "在尾部插入: " << val << endl;
    }
    
    void deleteNode(int val) {
        listNode* current = head;
        while (current) {
            if (current->data == val) {
                if (current->prev) {
                    current->prev->next = current->next;
                }
                else {
                    head = current->next;
                }
                if (current->next) {
                    current->next->prev = current->prev;
                }
                else {
                    tail = current->prev;
                }
                cout << "删除元素: " << val << endl;
                delete current;
                return;
            }
            current = current->next;
        }
        cout << "未找到元素: " << val << endl;
    }
    
    void insertAfter(int target, int val) {
        listNode* current = head;
        while (current) {
            if (current->data == target) {
                listNode* newNode = new listNode(val);
                newNode->next = current->next;
                newNode->prev = current;
                if (current->next) {
                    current->next->prev = newNode;
                }
                else {
                    tail = newNode;
                }
                current->next = newNode;
                cout << "在元素 " << target << " 后插入: " << val << endl;
                return;
            }
            current = current->next;
        }
        cout << "未找到目标元素: " << target << endl;
    }
    
    void insertBefore(int target, int val) {
        listNode* current = head;
        while (current) {
            if (current->data == target) {
                listNode* newNode = new listNode(val);
                newNode->prev = current->prev;
                newNode->next = current;
                if (current->prev) {
                    current->prev->next = newNode;
                }
                else {
                    head = newNode;
                }
                current->prev = newNode;
                cout << "在元素 " << target << " 前插入: " << val << endl;
                return;
            }
            current = current->next;
        }
        cout << "未找到目标元素: " << target << endl;
    }
    
    void insertAtPosition(int position, int val) {
        if (position <= 0) {
            insertAtHead(val);
            return;
        }
        listNode* current = head;
        for (int i = 0; i < position - 1 && current; ++i) {
            current = current->next;
        }
        if (!current) {
            insertAtTail(val);
        }
        else {
            listNode* newNode = new listNode(val);
            newNode->next = current->next;
            newNode->prev = current;
            if (current->next) {
                current->next->prev = newNode;
            }
            else {
                tail = newNode;
            }
            current->next = newNode;
            cout << "在位置 " << position << " 插入: " << val << endl;
        }
    }
    
    void printListForward() {
        listNode* current = head;
        cout << "正向遍历: ";
        while (current) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
    
    void printListBackward() {
        listNode* current = tail;
        cout << "反向遍历: ";
        while (current) {
            cout << current->data << " ";
            current = current->prev;
        }
        cout << endl;
    }
};

#endif